package com.company.algo.simpleOrhard;

import java.util.Arrays;

/**
 解法1：双指针 + 排序
 最终目的是让整个数组有序，那么我们可以先将数组拷贝一份进行排序，然后使用两个指针 i 和 j 分别找到左右两端第一个不同的地方，
 那么 [i, j]这一区间即是答案。

 解法2：双指针 + 线性扫描
 另外一个做法是，我们把整个数组分成三段处理。
 起始时，先通过双指针 i 和 j 找到左右两侧满足 单调递增 的分割点。
 即此时 [0, i]和 [j, n) 满足升序要求，而中间部分 (i, j)不确保有序。
 然后我们对中间部分[i,j]进行遍历：
    1.若nums[x]<nums[i-1]：由于[i,j]部分进行排序后nums[x]会出现在nums[i-1]后，将不满足整体排序，所以调整分割点i的位置
    2.若nums[x]>nums[j+1]，由于[i,j]部分进行排序后nums[x]会出现在nums[j+1]前，将不满足整体排序，所以调整分割点j的位置
 */
public class Shortest_unsorted_continuous_subarray {
    //双指针 + 排序
    public int findUnsortedSubarray(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i =0, j = nums.length - 1;
        while (i<=j && nums[i] == arr[i]) i++;
        while (i<=j && nums[j] == arr[j]) j--;
        return j-i+1;
    }
    //双指针 + 线性扫描
    public int findUnsortedSubarray2(int[] nums) {
        int MIN = -100005, MAX = 100005;
        int n = nums.length;
        int i = 0, j = n-1;
        while (i < j && nums[i] <= nums[i+1]) i++;
        while (i < j && nums[j] >= nums[j-1]) j--;
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int k = l; k <= r; k++) {
            if (nums[k] < min){
                while (i >= 0 && nums[i] > nums[k]) i--;
                min = i >= 0 ? nums[i]:MIN;
            }
            if (nums[k] > max){
                while (j<n && nums[j] < nums[k]) j++;
                max = j < n? nums[j]:MAX;
            }
        }
        return j == i ? 0 : (j-1) - (i+1) + 1;
    }

    public static void main(String[] args) {
        Shortest_unsorted_continuous_subarray Main = new Shortest_unsorted_continuous_subarray();
//        int[] nums = {1,2,2,2,2};
        int[] nums = {2,6,4,8,10,9,15};
//        int[] nums = {1,3,2,3,3};
        System.out.println(Main.findUnsortedSubarray2(nums));
    }
}
